package baseTest;

public class Manacher {
    public static void main(String[] args) {

    }

    public static int process(String s){
        if (s == null || s.length() == 0){
            return 0;
        }
        char[] chars1 = ManacherString(s);
        int[] ans = new int[chars1.length];
        int R = -1;
        int C = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < chars1.length; i++) {
           ans[i] = R > i ? Math.min(R-1,ans[2*C - i]) : 1;
           while (ans[i] + i < chars1.length && i-ans[i]>-1){
               if (ans[i]+1+1 == i-ans[i] -1){
                   ans[i]++;
               }else {
                   break;
               }
           }

           if (ans[i] +i > R){
              R =ans[i] + i;
              C = i;
           }
           max = Math.max(max,ans[i]);
        }
        return max;
    }
    public static char[] ManacherString(String s){
        char[] chars = new char[s.length()*2+1];
        int cur = 0;
        for (int i = 0; i < chars.length; i++) {
          chars[i] = (i&1) == 1 ? s.charAt(cur++) : '#';
        }
        return chars;
    }
}
